networkedlifeq21fandomcom-20200213-history
How to Position/Localize Indoors where GPS Can't Work? by Bhanu Sharma, Supanpreet Kaur, Karan Pahwa
1.1 Short Answer This ubiquitous piece of technology was not initially intended to be used by civilians, it was profoundly developed for military purposes. It was supposed to be exclusively for military, until President Ronald Reagan ordered a sudden change in policy in response to the deaths of 269 people aboard an airliner which was shot down by Soviets on 1 September 1983, believing it to be a military aircraft on a spying mission. Hence began a spiral of events which delivered to us the GPS, we rely on so much to day. It is to be pointed out that there are other Global Navigation Satellite Systems like Russia’s GLONASS, India’s GAGAN (which recently sent its 7th and final satellite to complete its full constellation). China is in the process of expanding its regional BeiDou Navigation Satellite System into the global Compass navigation system by 2020.1 The European Union's Galileo is a global GNSS in initial deployment phase, scheduled to be fully operational by 2020 at the earliest.2 India currently has satellite-based augmentation system, GPS Aided GEO Augmented Navigation (GAGAN), which enhances the accuracy of NAVSTAR GPS and GLONASS positions, and is developing the Indian Reginal Navigation Satellite System (IRNSS) to be known as navigation with Indian Constellation (NAVIC).GPS is used here as a compilation of various different GNSS systems, which work on similar principles. Positioning Systems like GPS, work extremely well in outdoor environments. The US Government claims to provide a “worst case” pseudo-range (pseudo-range is distance from satellite to receiver) accuracy of 7.8 meters at a 95% confidence level. The actual accuracy that users get is restricted by several other factors and is hence lower than this value 2. This accuracy will further decrease as we go into confined areas, like urban canyons, close to walls, buildings, trees and underground environments because signal from the satellites will be too weak to come across most buildings. In the end, the accuracy is so poor in Indoor localization that using GPS indoors becomes unreasonable. Here arises the need to develop a completely different system which can augment localization indoors. Indoor localization comes with its own set of restraints, like smaller dimensions, higher none line of sight (NLOS), high influence of obstacles like walls, trees, buildings, movement of human beings, and many other such factors 3. Multipath effects are also problematic in this scenario as signals are reflected and attenuated because of obstacles and this not only causes dispersion of information but also noise interference, which makes localization pretty tough. The electromagnetic waves travelling are scattered, reflected and absorbed by obstacles present in its path, hence hindering proper detection of signal. An effective Indoor position system will minimize the effects of these restrictions and accurately position an indoor topography or object or person, depending upon the need 4. For an indoor system to be in used for real time applications it should fulfill some performance criteria like accuracy, responsiveness, coverage, adaptiveness, scalability, cost and complexity. A large number of Indoor Positioning techniques have been developed like, infrared based systems, radio frequency identification, Bluetooth, FM, ultrasound based systems, etc. A system that gives accurate results in the least time span and is scalable is the best system. Most of the above mentioned techniques provide accurate results but they require a large additional infrastructure for their deployment. Therefore, these systems cannot be used widely as a significant cost is involved in their installation. Moreover, energy consumption and specific environment range limitations are also a great hindrance 5. IPS is not just hyper-refined version of GPS, but works on completely different concept. Though in a way it does take GPS forward. GPS cannot be used indoors due to three major effects namely, influence of obstacles, high non-line of sight and multi-path effect. IPS doesn’t use satellite communication like GPS, rather IPS uses nearby anchors (nodes with a known position), which either actively locate tags or provide environmental context for devices to sense. WiFi based positioning systems are widely deployed due to the fact that most of the devices are WiFi enabled. WLAN positioning systems measures the received signal strength from all the access points in the range of receiver. This received signal strength is measure by network interface cards (NICs) that are available in most devices. Thus, these devices are easy to locate without any additional hardware installation. In addition to it, even WLAN infrastructures doesn’t require any additional hardware to implement position algorithms. Therefore, cost is significantly reduced. Moreover, the number of devices being connected to WiFi at a particular location is not limited, which enables a large number of users to use positioning system. 1'.2 Long Answer' To determine user location using WLAN, three kinds of approaches are given below: * Strongest Base Station Model * Propagation Model * WLAN RSS Fingerprinting 1.2.1 Strongest Base Station Model In this method, user location is estimated based on the location of base station providing strongest signal strength from the set of known base stations. ] As shown in the fig.1, the location of client can be determined by calculating the signal strength from each access point. The client’s location is near the access point transmitting maximum signal strength. This method is quite simple but the accuracy is low as it doesn’t determine the exact location of the user rather it gives you an idea that the user is close to the access point from which it is getting maximum signal strength. The complexity of indoor environments affects it accuracy to a great extent. 1.2.2 Propagation Model In this technique, signal path loss is used to determine the user location, which is determined by received signal strength information. Received signal strength (RSS) is estimated when the transmitter and receiver have unbarred line-of-sight path (LOS). The transmitted and the received powers are known and the received power strength is decreased with the square of the distance. Received power strength, Pt = 1/D², where D is the distance between the transmitter and the receiver. To find the co-ordinates of the mobile user propagation model uses two different techniques: 1.Triangulation 2.Trilateration 1.2.2.1 Triangulation To determine the user location, geometric properties of triangles are used. In this method, we require one known side of the triangle on two known angles. To determine the user’s location in 2D plane at least 2 reference points are required. The location of these reference points and the distance between the is known. By using directional antennas or antenna arrays the angle of the received signal from known reference points to the user’s location can be found. These angles are then used to determine the user’s location7. ] As illustrated in the above fig.2, the angle of arrival (AOA) of two reference points (angle 1 and angle 2) tare calculated using antenna array. AOA is the angle between the transmission route of an incident wave and some reference direction, which is known as orientation. Orientation, a ﬁxed direction against which the AOAs are measured, is represented in degrees in a clockwise direction from the North. As shown if fig.3, the antennas are equidistant separated by distance “s”. The incident signal is arriving on antenna array through propagation paths. AOA is computed using the phase-shift difference of the incident signal. ] When the orientation of the user is known as shown in fig.4, angle θ1 from b1 and angle θ2 from b2, the relative AOAs can be measured at unknown position U. Then orientation of U is assumed to be ∆θ, therefore, the absolute AOAs can be measured as (θi +∆θ)(mod 2 π ),i = {1,2}. The estimated position of user U is the juncture of all rays when two or more non-collinear reference points are present 9. ] When the orientation of the user is unknown, at least 3 reference points are required to estimate the user’s location. The absolute AOAs can be calculated using the relative AOAs ∠b1ub2, ∠b1ub3 and ∠b2ub3. Since a chord subtends equal angles, if three points and the chord joining them is known, the intersection of the arcs will determine the user’s location. As shown in the given fig.5, the angle ∠b1ub3 and the chord b1b3 confine user’s position on the arc passing through b1, u and b3. The location of user u can be determined by the intersection of all the arcs 9. ] 1.2.2.2 Trilateration It is also known as range technique, since the user’s location is estimated from distance measurements. In this method received signal strength from sender node to receiver node is measured from at least three reference points. The propagation time, that is directly proportional to the propagation distance of signal, from reference points to user is measured. Time synchronization of all the reference points is mandatory. This technique estimates user’s location using time of arrival (TOA). The arrival time of signal at the receiver is measured based on the accurate synchronization of the reference points from where signal is transmitted. The distance between the user and the known reference points is calculated by the arrival time and the corresponding speed of signal. ] In fig.5, three reference points b1, b2 and b3 (co-ordinates are X1Y1, X2Y2 and X3Y3 respectively) are known. The distance of user from the three reference point is computed from propagation time delay of signal. The user’s co-ordinates (X Y) can be calculated by computing the intersection point of the three circles. Consider the equation of circle as r2=x2+y2. For a circle centered at XaYa is r2= (x- Xa)2+(y-Ya)2. Similarly, the equations can be found for each circle. Circle 1: r12 = (x- X1)2+(y-Y1)2 Circle 2: r22= (x- X2)2+(y-Y2)2 Circle 3: r32= (x- X3)2+(y-Y3)2 The intersection point of the three circles can be calculated by solving the three equations and finding the point that satisfies all the three equations.The propagation model is quite simple and easy to deploy. But it is not very efficient when high accuracy and precision is required due to the noise in the wireless signal and the influence of obstacles in indoor environment 5. 1.2.3 WLAN RSS Fingerprinting: RSS based positioning systems are being widely deployed as they are simple and easy to install and there is no additional infrastructure required that allows it to fit in low budget. RSS fingerprinting is tolerant to wireless signal noise, therefore, it is most exploited technique now-a-days. In WLAN RSS fingerprinting the received signal strength is measured at all reference points. The RSS data is used to determine the distance between the transmitter and the receiver. This distance is calculated depending upon the conduct of signal transmission and evidence of the building 10. Fingerprinting has two phases: offline phase and online phase. WLAN RSS Offline Phase: In this phase the RSS is calculated at all reference points and the data is stored in a training database. Consider n access points (transmitters), and r reference points. At each reference point the RSS is calculated from each of the n access points and the data is then stored in the training database. In fig.7, the RP are the reference points whose x and y co-ordinates are known and RSS values corresponding to each access point is calculated and then stored in the database. There is one major problem encountered in this phase. The number of fingerprints are sometimes insufficient to accurately estimate the position of the mobile user. To overcome this problem the concept of extrapolation and interpolation is used 12. WLAN RSS online phase: After acquiring the training database, actual detection of the mobile user can be carried out. The online determination phase can be easily explained using figure 7. The RSS vector associated with the mobile user at any unknown location is measured by using the reference points present in the building. This RSS vector is then compared to the wireless RSS vector records in the training database. Then by using various positioning algorithms, we can predict the most likely location of the mobile user. There are various positioning algorithms which can be used for WLAN RSS fingerprinting approaches. These include, nearest neighbor method and probabilistic estimation.The nearest neighbor or K nearest neighbor (KNN) is one of the most basic techniques employed for Indoor positioning. After picking up the RSS vector in the training database which matches the observed RSS profile the most, the Euclidean distance determination method is used to find user location 5. It is one of the simplest methods employed for RSS fingerprinting, where the distance between the online RSS value and the offline RSS training database is calculated. Di is the distance Euclidean Distance between the mobile user and the RSS vectors present in the training database, n ''is the number of APs, RSSi is the ''ith AP’s signal strength received in the online phase. RSSi' is RSS value stored in the training phase. The location is detected by averaging the RSS vector of the K nearest neighbor with the minimum Euclidean distance. Hence, this algorithm using a well-defined Euclidean Distance metric declares an actual point in physical space as the current location of the mobile user. However it should be kept in mind that though this is a relatively simple method which does provide a somewhat accurate answer, it does have some problems associated with it. This algorithm can provide multiple outcomes, and if such is the case then some complicated resolving methodologies need to be used. Also, the accuracy is dependent on the reference database granularity. For more accuracy we need finer grid, which will mean a much larger database, which is quite difficult obtain in some situations 11. Moreover the Euclidean distance does not provide adequate performance in cases where distribution of the RSS vectors included in fingerprints are non-convex and multi-modal 13, which is the case in indoor environment because of high Non Line of Sight and presence of people. The value of K, that is, the number of neighbors, influences the resulting accuracy, if value of K is 1, the algorithm will deduce the nearest neighbor. A slight improvement to KNN is distance-weighted K nearest Neighbor (WKNN), where the basic idea is to assign weights to different neighbors. The closer the neighbor, higher is the weight assigned to it. Probabilistic Estimation: 'KNN provides good performance and accuracy under most conditions 11, but it lacks accuracy when the number of reference points are limited. Also in complex indoor environment, the variation if the measured RSS value at each reference point can be quite large, hence hindering the detection process. There are various probabilistic method which produce Maximum Likelihood (ML), Maximum A Posteriori (MAP), or Minimum Mean Square Error (MMSE) estimates of position using estimates of likelihood and posterior density functions 13. Bayes rule determination method is also used for finding the highest probability where the mobile user can be present 5. The most probable location li can be found out using Bayes Rule, which tries to maximize the conditional probability, ''p(li/RSS). It can be calculated as follows: In this equation, p(li/RSS) is the conditional probability of obtaining the RSS at'' ith'' position li ''given that the mobile user is present at the position ''li. p(li) is the prior probability calculated if the mobile user is located at position li '',p(RSS) does not depend on location ''li and is often regarded as the normalizing constant. There are various methods which can be used for online matching of test RSS vector values with the collected fingerprints, besides KNN and probabilistic methods, there are also Kernel, and Support Vector Regression (SVR) methods. But for the sake of simplicity only first two methods are discussed here. '''1.3 Additional References [Schneider, New Indoor Navigation Technologies Work Where GPS Can’t. IEEE Spectrum, 20 Nov 2013.|[1David Schneider, New Indoor Navigation Technologies Work Where GPS Can’t. IEEE Spectrum, 20 Nov 2013.]] [Accuracy, GPS.gov|[2GPS Accuracy, GPS.gov]] [Indoor Location Determination, in Location-Based Services Handbook, CRC Press, 2010.|[3J.Yiming, Indoor Location Determination, in Location-Based Services Handbook, CRC Press, 2010.]] [Advances in Wireless Indoor Localization Techniques and System, Journal of Computer Networks and Communications Volume 2013 (2013), Article ID 185138, 12 pages Zahid Farid, Rosdiadee Nordin, and Mahamod Ismail|[4Recent Advances in Wireless Indoor Localization Techniques and System, Journal of Computer Networks and Communications Volume 2013 (2013), Article ID 185138, 12 pages Zahid Farid, Rosdiadee Nordin, and Mahamod Ismail]] [Jiang, “A WLAN Fingerprinting Based Indoor Localization Technique”. |[5 Landu Jiang, “''A WLAN Fingerprinting Based Indoor Localization Technique”.]] '' [Aweya, Luis Orozco BARBOSA, “Method and system for wireless LAN-based indoor position location”,United States Patent, US 8,165,150 B2, Apr. 24, 2012.|[6James Aweya, Luis Orozco BARBOSA, “''Method and system for wireless LAN-based indoor position location''”,United States Patent, US 8,165,150 B2, Apr. 24, 2012.]] [Disha M,”A Comparative Analysis on indoor positioning Techniques and Systems”, International Journal of Engineering Research and Applications, Vol. 3, Issue 2, March -April 2013.|[7Adalja Disha M,”''A Comparative Analysis on indoor positioning Techniques and Systems''”, International Journal of Engineering Research and Applications, Vol. 3, Issue 2, March -April]] https://en.wikipedia.org/wiki/Wi-Fi_positioning_system [P and M. L. Sichitiu, "Angle of Arrival Localization for Wireless Sensor Networks," 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, Reston, VA, 2006, pp. 374-382.|[8R. P and M. L. Sichitiu, "Angle of Arrival Localization for Wireless Sensor Networks," 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, Reston, VA, 2006, pp. 374-382.]] [Alhmiedat, Ghassan Samara, Amer O. Abu Salem,” An Indoor Fingerprinting Localization Approach for ZigBee Wireless Sensor Networks”, European Journal of Scientific Research ISSN 1450-216X / 1450-202X Vol. 105 No 2 July, 2013. |[9Tareq Alhmiedat, Ghassan Samara, Amer O. Abu Salem,” An Indoor Fingerprinting Localization Approach for ZigBee Wireless Sensor Networks”, European Journal of Scientific Research ISSN 1450-216X / 1450-202X Vol. 105 No 2 July, 2013.]] [[ A Comparative Performance Evaluation of RSS-Based Positioning Algorithms Used in WLAN Networks Ahmad Hatami and Kaveh Pahlavan Center for Wireless Information Network Studies Worcester Polytechnic Institute (WPI).|10 A Comparative Performance Evaluation of RSS-Based Positioning Algorithms Used in WLAN Networks Ahmad Hatami and Kaveh Pahlavan Center for Wireless Information Network Studies Worcester Polytechnic Institute (WPI).]] [Interpolation and Extrapolation Methods for RSS-Based Localization With Indoor Wireless Signals Jukka Talvitie, Markku Renfors, Fellow, IEEE, and Elena Simona Lohan, Member, IEEE|[11 Distance-Based Interpolation and Extrapolation Methods for RSS-Based Localization With Indoor Wireless Signals Jukka Talvitie, Markku Renfors, Fellow, IEEE, and Elena Simona Lohan, Member, IEEE]] [Positioning in Wireless Local Area Networks Azadeh Kushki, Student Member, IEEE, Konstantinos N. Plataniotis, Senior Member, IEEE, and Anastasios N. Venetsanopoulos, Fellow, IEEE|[12 Kernel-Based Positioning in Wireless Local Area Networks Azadeh Kushki, Student Member, IEEE, Konstantinos N. Plataniotis, Senior Member, IEEE, and Anastasios N. Venetsanopoulos, Fellow, IEEE]] __FORCETOC__ __NEWSECTIONLINK__